/**
 * Created by L.jp
 * Description:请实现一个函数用来匹配包括'.'和'*'的正则表达式。
 * 1.模式中的字符'.'表示任意一个字符
 * 2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。
 * 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
 * User: 86189
 * Date: 2022-09-03
 * Time: 17:23
 */
public class Solution {
    public boolean match (String str, String pattern) {
        //分为两种情况
        //1.p的第j个字符不是'*',那么就看s和j对应字符是否相等，如果相等或者p的第j个字符是'.',那么就看s和j的前几个字符是否相等,如果不相等那么肯定是false
        //2.p的第j个字符是'*',但是p是'*'，所以又分为三种情况：因为*号代表可以让它前面的一个字符出现0,1，无数次
        //  a.匹配0次：让p的第j-1个字符出现0次才能和s字符串匹配的话，那么就要看p的前j-2个字符是否和s的前i个字符相等，也就是dp[i][j]=dp[i][j-2];
        //  b.匹配1次：让p的第j-1个字符出现一次才能和s字符串匹配的话，那么就要看p的前j-1个字符是否和s的前i个字符相等，也就是dp[i][j]=dp[i][j-1];
        //  c.匹配无数次： 让p的第j-1个字符出现无数次或者多次才能和s字符串匹配的话，那么就只需要看s的前i-1个字符是否和p的前j个字符是否相等，也就是的dp[i][j]=dp[i-1][j];
    
        //这三种情况，p中的*号都是和他的前一个字符相互捆绑的，需要一起配合才会出现效果，所以无论匹配0,1，无数次，*号都可以看成*号本身不存在，他只是可以变出0,1，无数个j-1个字符
    
        int n=str.length();
        int m=pattern.length();
        //dp[i][j]表示s的前i个字符是否和p的前j个字符匹配
        boolean[][] dp=new boolean[n+1][m+1];
        //初始化，空串和空串匹配
        dp[0][0]=true;
        //初始化，如果p串为空，s串不为空，那么肯定是false，无论什么情况都是false,所以就利用dp的初始值即可
        //如果s串为空，p串不为空，那么p串就可以利用*号和他匹配，但是*号不能出现在p串的第一个字符，因为他的功能就是让*号的前一个字符出现0，1，无数次，如果前面没有字符，那么功能就不会生效，反而这个*号无法消除，所以*号出现的位置必须是大于等于第2个字符
    
        for(int j=2;j<=m;j++){
            if(pattern.charAt(j-1)=='*'){
                //要使*号前面的字符出现0次，那么就要看前j-2个字符是否和空串匹配
                dp[0][j]=dp[0][j-2];
            }
        }
        //不是空串的普通情况，分为p的当前字符是否是*号两种情况讨论
        //s,p串都从第1个字符开始
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //这里的i和j都是长度，那么在字符串函数中，使用下标就要使对应的长度减1
                if(pattern.charAt(j-1)!='*'){
                    //如果s和j的对应字符相等，或者j的字符是‘.’,那么就看前一个转态
                    if(pattern.charAt(j-1)=='.' || pattern.charAt(j-1)==str.charAt(i-1)){
                        dp[i][j]=dp[i-1][j-1];
                    }
                
                }else{
                    //p当前字符是*号，那么就要看*号的前一个字符和s的第i个字符是否相等，并且*号的前一个字符不能是'.'
                    if(pattern.charAt(j-2)!=str.charAt(i-1) && pattern.charAt(j-2)!='.'){
                        dp[i][j]=dp[i][j-2];
                    }else{
                        //如果*号的前一个字符和s的第i个字符不相等，但是*号前面的一个字符是普通字符
                        dp[i][j]=dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
}
